

n= 97241687856288022837177610505474532920656529642426470579724842296171122463562033567892528254068437405428440047443077130250424970479245272044234333326157389730675399189215605021729743543783225715067575504290579078900712844037541526596124022874295596594165443599059261336412419108831673380989664152170339815353
x= 76251226957596065751905501662402714391923850671867587167464085925173286522128503644296272628038847533871948570810739817877627713102159932430977709909748370901981421404879324499805866947441634629133466750719537347251379178552696374741833759800308308127962083506879382823970512761991493938852957690250878322578
y= 12253642759105670010364762256856901873217636903279146850471983391803634662567498475625897078060483924018212440847903877051459084988721440013876221852155876093538832782554356365910569058291093320791214726009048684596824327262265645350891891024869722687889041883533675278821269777332741484379078221002036976820

import libnum
#结论1： p=gcd(x**n%n-y,n)
#x^n%n  ^ =>xor  # ^ 次方
p= libnum.gcd((pow(x,n,n)-y),n)
print(p)
q=n//p
print(n==p*q)

#x=pow(m,p,n)
d=libnum.invmod(p,(p-1)*(q-1))
m=pow(x,d,n)
print(libnum.n2s(m))

# d=libnum.invmod(p,p-1)
# m=pow(x,d,p)
# print(libnum.n2s(m))

# d=libnum.invmod(q,q-1)
# m=pow(y,d,q)
# print(libnum.n2s(m))